package com.zp.self.module.level_4_算法练习.算法.动态规划;

/**
 * @author By ZengPeng
 */
public class 力扣_63_不同路径II {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_63_不同路径II().uniquePathsWithObstacles(new int[][]{{0,0,0},{0,1,0},{0,0,0}}));
        System.out.println(new 力扣_63_不同路径II().uniquePathsWithObstacles(new int[][]{{0,1},{0,0}}));
    }

    /**
    题目：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
     机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
     现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
     网格中的障碍物和空位置分别用 1 和 0 来表示。

     示例 1：
     输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
     输出：2
     解释：3x3 网格的正中间有一个障碍物。
     从左上角到右下角一共有 2 条不同的路径：
     1. 向右 -> 向右 -> 向下 -> 向下
     2. 向下 -> 向下 -> 向右 -> 向右

     示例 2：
     输入：obstacleGrid = [[0,1],[0,0]]
     输出：1

    分析：【perfect】嘶~,动态规划都这么慢？
       1.动态规划：同 力扣_62_不同路径 一样使用动态规划，数组记录。
            区别再于根据位置，判断此处能否前进。 -- 执行用时：3 ms, 在所有 Java 提交中击败了5.96%的用户
        2.转换递归为迭代 ：这里表达式要改变一下fun(n,m) =  fun(n-1,m) + fun(n,m-1)  --换了种思维
    边界值 & 注意点：
       1.
     **/
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //2.动态规划+循环
        int[][] numb = new int[obstacleGrid.length][obstacleGrid[0].length];
        //初始化第一行、第一列，因为都只能直着走，只有1中方法
        for (int i = 0; i < numb.length && obstacleGrid[i][0] == 0; i++)  numb[i][0] = 1;
        for (int i = 0; i < numb[0].length && obstacleGrid[0][i] == 0; i++)  numb[0][i] = 1;

        for (int i = 1; i < numb.length; i++) {
            for (int j = 1; j < numb[i].length; j++) {
                if(obstacleGrid[i][j]==0)
                    numb[i][j]=numb[i-1][j]+numb[i][j-1];
            }
        }
        return numb[obstacleGrid.length-1][obstacleGrid[0].length-1];

        //1动态规划+递归
       /* int[][] numb = new int[obstacleGrid.length][obstacleGrid[0].length];
        return recursion(0,0,obstacleGrid,numb);*/
    }

    //递归
    private int recursion(int m, int n,int[][]obstacleGrid, int[][] numb) {
        if(numb[m][n]!=0) return numb[m][n];
        if(obstacleGrid[m][n]==1) return 0;
        if(m==numb.length-1 && n==numb[0].length-1) return 1;
        int sum = 0;
        if(m<numb.length-1)
            sum +=  recursion( m+1,  n, obstacleGrid, numb);
        if(n<numb[0].length-1)
            sum +=  recursion( m, n+1,obstacleGrid,  numb);
        numb[m][n] =sum;
        return sum;
    }
}
